package com.lw.leetcode.tree.b;

import com.lw.leetcode.tree.TreeNode;

import java.util.ArrayDeque;
import java.util.LinkedList;
import java.util.Queue;

/**
 * 662. 二叉树最大宽度
 *
 * @Author liw
 * @Date 2021/5/12 12:47
 * @Version 1.0
 */
public class WidthOfBinaryTree {

    public static void main(String[] args) {
        WidthOfBinaryTree test = new WidthOfBinaryTree();
        Queue<TreeNode> a = new ArrayDeque<>();
//        a.add(null);


        Queue<TreeNode> b = new LinkedList<>();
        ((LinkedList<TreeNode>) b).add(null);

    }
    public int widthOfBinaryTree(TreeNode root) {
        LinkedList<TreeNode> a = new LinkedList<>();
        LinkedList<Integer> a1 = new LinkedList<>();
        LinkedList<TreeNode> b = new LinkedList<>();
        LinkedList<Integer> b1 = new LinkedList<>();
        a.add(root);
        a1.add(0);
        int max = 1;
        while (!a.isEmpty()) {
            while (!a.isEmpty()) {
                TreeNode poll = a.poll();
                int index = a1.poll();
                if (poll.left != null) {
                    b.add(poll.left);
                    b1.add((index << 1));
                }
                if (poll.right != null) {
                    b.add(poll.right);
                    b1.add((index << 1) + 1);
                }
            }
            if (!b.isEmpty()) {
                max = Math.max(max, b1.getLast() - b1.getFirst() + 1);
            }
            a = b;
            a1 = b1;
            b = new LinkedList<>();
            b1 = new LinkedList<>();
        }
        return max;
    }
}
